A variety of network architectures are available for designing and implementing a telecommunications network. The ring topology is found very frequently in network architectures. There are a number of topology discovery algorithms and commercial solutions for general logical topologies. Some examples are spanning tree algorithms for Ethernet and shortest path algorithms for general graph theory. There is, however, less focus on the specific ring architecture and the physical ring topology. The dual ring topology offers numerous advantages over a single ring topology, such as reliability and bandwidth flexibility to name a few. A telecommunications network in the dual ring topology uses two physically separated rings (also called ringlets), one for each traffic direction, clockwise (CW) and counter-clockwise (CCW), as shown in FIG. 1. In the figure, five stations (also called nodes), A1 to A5, are connected in a dual ring which comprises CW (clockwise) ring 10 and CCW (counter clockwise) ring 12.
The bi-directional ring allows for two protection mechanisms to be implemented in case of media failure, such as link failure, or station failure, one being the ring wrap in FDDI (fiber distributed data interface) or SONET/SDH BLSR (Bi-directional Line Switched Ring) and another being the source steering in SONET UPSR (Unidirectional Path Switched Ring) where the source station selects which ringlet will carry the packet. The ring wrap basically consists in making a U-turn when a link failure is encountered. FIG. 2 shows an example of wrapping: when a failure 20 on a link is detected, station A2 wraps all the traffic which is to go on the failed link back onto the other link as depicted by numeral 22. In the source steering, all the stations are made aware of a failure on one ring and any affected traffic is steered to the remaining ring at the source station.
In the management of a ring network, problems consist in making sure that every station in the ring is aware of the current ring topology (locations and identifications of all other stations, link status between stations, current station or link failures, recovery of failures, etc.). At initialisation of the network, there is a discovery phase where all the stations fill their empty database. Then, there are database updates due to a new station insertion or an existing station removal, or due to a link or station failure. The database of each station needs to be adjusted accordingly. All the local databases must be synchronized as quickly as possible. Also, it is best to have a simple and non-centralized solution. The associated control information should be resilient itself to failures and should minimize usage of the bandwidth as well as the time needed to propagate the information.
U.S. Pat. No. 5,590,124 Dec. 31, 1996 Robins describes a protocol for a ring interconnect architecture which defines data exchange operations (e.g., GET and PUT operations) between components associated with different stations on the ring. The patent also describes a topology discovery protocol which uses data exchange operations for such a purpose. This protocol allows an instigator station to use the data transfer protocol to determine the topology of the ring architecture to which it is coupled. The protocol is not believed to be able to operate when one or more connections have failed in the ring. The patent is totally silent about such eventuality.
A new IEEE protocol is in the process of being standardized (802.17) for a flexible and resilient dual ring topology which is called Resilient Packet Ring (RPR for short) and is a MAC layer protocol dedicated to ring architectures, especially for underlying Metro optical networks. The protocol also features a ring discovery method which requires that the system should be entirely plug-and-play. This means that the stations on the ring have to discover by themselves what other stations are on the ring, and at what distance.
Early 2002, there were two drafts for the RPR standard (named Darwin and Alladin). Both drafts for RPR contain discovery algorithms. Darwin relies on broadcasting expanding control messages; that is to say, each station either originates a message or appends its own description to each message it receives from others. At the end of its life, each message has expanded up to contain the description of all the stations in the ring. Updates are activated upon certain events (station/link status change, validation failure, timer expiration, etc.).
Alladin is based on two different kinds of messages (Hello and Status) and a database version number of each station. Hello messages are used by a station to transmit its database version number to its neighbors only. Status messages are broadcast by a station to update its status and version numbers of all other stations on the ring, whenever there is a change of its status or a failure of connecting links.
An IEEE draft (802.17/D1.0) for RPR was published in August 2002 and it contains a topology discovery protocol. According to the protocol, at bring up, at any point that a station detects a change in local status, at any point that a station detects a new station on the ring, upon a change in protection status, and periodically a station broadcasts a topology message to all stations on the ring. The message contains all the information about the local station and when a station receives the message it updates its local topology image.
Applicant's earlier filed application entitled “Topology Management Of Dual Ring Network”, filed Nov. 26, 2002, in the United States Patent Office, describes another topology discovery algorithm. The algorithm uses only one discovery packet format and a set of timer settings, which controls a variety of actions at a station on the ring. Under the control of a variety of timer settings, a station periodically broadcasts discovery packets to all the stations on the ring so that database at each station can be continually up to date and constantly monitors the neighboring stations operation by sending a discovery packet to them. The discovery packets contain the description of only one station and two links to neighboring stations. This algorithm therefore relies on sending continuously a small flow of information. It has the advantage of being resilient, simple and of not using too much bandwidth, which makes its propagation faster. The algorithm should still be operational in case there are several link failures in the ring and the wrapping is not implemented.
The IEEE draft (802.17/D1.0) mentioned above contains some requirements with regards to the topology discovery mechanism. They are that the method should converge in about a round trip time (RTT) in normal operation, RTT being the time it takes for a packet to traverse all the stations around the ring, and that it has to discover the topology in special situations (one of the rings or the two being cut, a station being isolated, etc.).
The above solutions (Darwin and Alladin) do not cope well with misbehaving topologies, in which one or more stations are isolated. The above mentioned Applicant's earlier filed application describes an algorithm which addresses this problem.
Also, most algorithms, including those discussed above take a round trip time to converge in normal operation, whereas the algorithm according to this invention takes only about half of the RTT, by using the two directions of the ring in an interdependent fashion. In the present invention, messages are exchanged between two neighboring stations, that is to say, messages are terminated and originated and are never forwarded. Therefore, there is no broadcast storm. The invention is easier to detect failure and it has a fewer messages to process.
While the invention is described specifically in reference to RPR, it should be noted that it could be used in any kind of ring-oriented architecture as long as it features at least two counter-rotating rings.